class PalindromeList {
public:
    typedef struct ListNode Node;
    Node* reverse(Node* head)
    {
        Node* cur = head;
        Node* pre = NULL;
        while (cur)
        {
            Node* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    bool chkPalindrome(ListNode* A) {
        if (A->next == NULL)
        {
            return true;
        }
        Node* fast = A;
        Node* slow = A;
        Node* prev = A;
        while (fast && fast->next)
        {
            prev = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        Node* p1 = A;
        Node* p2 = NULL;
        if (fast == NULL)
        {
            p2 = reverse(slow);
            prev->next = NULL;
        }
        else
        {
            p2 = reverse(slow->next);
            prev->next = NULL;
        }
        while (p1 && p2)
        {
            if (p1->val != p2->val)
            {
                return false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        if (!p1 && !p2)
        {
            return true;
        }
        return false;
    }
};